//The n-queens puzzle is the problem of placing n queens on an n x n chessboard 
//such that no two queens attack each other. 
//
// Given an integer n, return the number of distinct solutions to the n-queens p
//uzzle. 
//
// 
// Example 1: 
//
// 
//Input: n = 4
//Output: 2
//Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
//
// 
//
// Example 2: 
//
// 
//Input: n = 1
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// 1 <= n <= 9 
// 
// Related Topics 回溯算法 
// 👍 258 👎 0


package leetcode.editor.cn;

//Java：N-Queens II
class P52NQueensIi {
    public static void main(String[] args) {
        Solution solution = new P52NQueensIi().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int count = 0;

        public int totalNQueens(int n) {
            char[][] matrix = new char[n][n];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    matrix[i][j] = '.';
                }
            }
            solveNQueens(matrix, 0);
            return count;
        }

        private void solveNQueens(char[][] matrix, int row) {
            if (row == matrix.length) {
                count++;
                return;
            }
            for (int col = 0; col < matrix[0].length; col++) {
                if (isValid(row, col, matrix)) {
                    matrix[row][col] = 'Q';
                    solveNQueens(matrix, row + 1);
                    matrix[row][col] = '.';
                }
            }
        }

        /* 是否可以在 board[row][col] 放置皇后 */
        boolean isValid(int row, int col, char[][] board) {
            int n = board.length;
            // 检查列是否有皇后互相冲突
            for (int i = 0; i < n; i++) {
                if (board[i][col] == 'Q') {
                    return false;
                }
            }
            // 检查右上⽅是否有皇后互相冲突
            for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
                if (board[i][j] == 'Q') {
                    return false;
                }
            }
            // 检查左上⽅是否有皇后互相冲突
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                if (board[i][j] == 'Q') {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}